package sword_offer;

import java.util.*;

/**
 * @author Synhard
 * @version 1.0
 * @class Code47
 * @description 剑指 Offer 45. 把数组排成最小的数
 * 输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
 *
 *  
 *
 * 示例 1:
 *
 * 输入: [10,2]
 * 输出: "102"
 * 示例 2:
 *
 * 输入: [3,30,34,5,9]
 * 输出: "3033459"
 *  
 *
 * 提示:
 *
 * 0 < nums.length <= 100
 * 说明:
 *
 * 输出结果可能非常大，所以你需要返回一个字符串而不是整数
 * 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-07-10 7:27
 */
public class Code47 {
    public static void main(String[] args) {
        int[] nums = new int[]{3,30,34,5,9};
        System.out.println(minNumber(nums));
    }

    public static String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            strs[i] = String.valueOf(nums[i]);
        }
        quickSort(strs, 0, strs.length - 1);
        StringBuilder sb = new StringBuilder();
        for (String s : strs) {
            sb.append(s);
        }
        return sb.toString();
    }

    private static void quickSort(String[] strs, int left, int right) {
        if (left < right) {
            int pivot = partition(strs, left, right);
            quickSort(strs, left, pivot);
            quickSort(strs, pivot + 1, right);
        }
    }

    private static int partition(String[] strs, int left, int right) {
        String temp = strs[left];
        while (left < right) {
            while (left < right && Long.parseLong(temp + strs[right]) <= Long.parseLong(strs[right] + temp)) {
                right--;
            }
            strs[left] = strs[right];
            while (left < right && Long.parseLong(temp + strs[left]) >= Long.parseLong(strs[left] + temp)) {
                left++;
            }
            strs[right] = strs[left];
        }
        strs[left] = temp;
        return left;
    }
}

/*
本质上是一个排序的问题
只要 x + y < y + x 那么 x 就应该排在 y 的前面
 */